#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void Print(const vector<int>& vecArr) {

	for (int i = 0; i < vecArr.size(); ++i) {
		cout << vecArr[i] << ' ';
	}
	cout << endl;
}
void siftDown(vector<int>& vecArr, int cur, int n) {

	while (cur < n) {
		int large = cur;
		int left = cur * 2 + 1;
		int right = cur * 2 + 2;
		if (left < n && vecArr[large] < vecArr[left]) {
			large = left;
		}
		if (right < n && vecArr[large] < vecArr[right]) {
			large = right;
		}
		if (large != cur) {
			swap(vecArr[large], vecArr[cur]);
			cur = large;
		}
		else {
			break;
		}
	}
}
void heapSort(vector<int>& vecArr) {

	int n = vecArr.size();
	for (int i = n / 2 - 1; i >= 0; --i) {
		siftDown(vecArr, i, n);
	}

	for (int i = n - 1; i > 0; --i) {
		swap(vecArr[i], vecArr[0]);
		siftDown(vecArr, 0, i);
	}
}
int main() {

	vector<int> vecArr({ 2,1,5,3,2,10 });
	Print(vecArr);
	heapSort(vecArr);
	Print(vecArr);
	return 0;
}